BZOJ4069【APIO2015】巴厘岛的雕塑 < DP >

Problem

【APIO2015】巴厘岛的雕塑

Description

印尼巴厘岛的公路上有许多的雕塑,我们来关注它的一条主干道。
在这条主干道上一共有座雕塑，为方便起见，我们把这些雕塑从到连续地进行标号，其中第 i 座雕塑的年龄是年。为了使这条路的环境更加优美，政府想把这些雕塑分成若干组，并通过在组与组之间种上一些树，来吸引更多的游客来巴厘岛。
下面是将雕塑分组的规则：
这些雕塑必须被分为恰好组，其中，每组必须含有至少一个雕塑，每个雕塑也必须属于且只属于一个组。同一组中的所有雕塑必须位于这条路的连续一段上。
当雕塑被分好组后，对于每个组，我们首先计算出该组所有雕塑的年龄和。
计算所有年龄和按位取或的结果。我们这个值把称为这一分组的最终优美度。
请问政府能得到的最小的最终优美度是多少?

Input

输入的第一行包含三个用空格分开的整数。
第二行包含个用空格分开的整数。

Output

输出一行一个数，表示最小的最终优美度。

Sample Input

6 1 3
8 1 2 1 5 4

Sample Output

11

Explanation

将这些雕塑分为组，和，它们的和是和，最终优美度是。不难验证，这也是最终优美度的最小值。

HINT

子任务编号				分值

标签：DP

Solution

奇葩的面向数据编程题。

由于算答案是按位或，可以考虑从高位向低位贪心，每次判断在前面的位都取到最优情况下，这一位能否取。这个判断的过程可以实现。
表示考虑前个雕塑，分成个组，能否在当前位上取。
那么当且仅当，满足，并且和当前答案取或的结果还是当前答案（即不会使得前面位上不为最优解），还需要在当前位上的值为（这样当前位才能取）。
求出所有后，判断是否满足，如果存在则可以取，否则此位取。

然而这样并不能得满分。上面的方法是处理出所有值，不能通过的。

而对于，发现，则每次使得分的组数量尽量小肯定是最优的。于是用表示当前位考虑前个雕塑，最少需要分成几组才能使当前位上可以取。如果在当前位处理后发现，那么必须取，否则可以取。这样复杂度降成了，可以解决。

综上，特判数据分两种情况分别做即可。

Code

#include <bits/stdc++.h>
#define MAX_N 2000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, A, B; lnt s[MAX_N+5], ans;
bool f[MAX_N+5][MAX_N+5]; int g[MAX_N+5];
void sub1() {
    for (int p = m, flag = 1; p; p--, flag = 1) {
        memset(f, false, sizeof f), f[0][0] = true;
        for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++)
            for (int k = j-1; k < i; k++) if (f[k][j-1]) {
                if ((((s[i]-s[k])>>p)|ans)^ans) continue;
                if ((s[i]-s[k])&(1LL<<(p-1))) continue;
                f[i][j] = true; break;
            }
        for (int i = A; i <= B; i++)
            if (f[n][i]) {flag = 0; break;}
        (ans <<= 1) |= flag;
    }
    printf("%lld\n", ans);
}
void sub2() {
    for (int p = m; p; p--) {
        memset(g, 0x3f, sizeof g), g[0] = 0;
        for (int i = 1; i <= n; i++) for (int k = 0; k < i; k++) {
            if ((((s[i]-s[k])>>p)|ans)^ans) continue;
            if ((s[i]-s[k])&(1LL<<(p-1))) continue;
            g[i] = min(g[i], g[k]+1);
        }
        (ans <<= 1) |= (g[n] > B);
    }
    printf("%lld\n", ans);
}
int main() {
    read(n), read(A), read(B);
    for (int i = 1; i <= n; i++)
        read(s[i]), s[i] += s[i-1];
    for (lnt i = s[n]; i; i >>= 1) m++;
    return (A != 1 ? sub1() : sub2()), 0;
}